package leetcode.array;

import java.util.*;

/**
 * @description:三数之和 2021-11-20
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * @author: cyy
 **/
public class threeNum {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeNum(nums);
        for (int i = 0; i < lists.size(); i++) {
            List<Integer> anInt = lists.get(i);
            for (int num : anInt) {
                System.out.println("result:" + num);
            }
        }

        //冒泡排序  -4, -1,-1, 0, 1, 2
//        int temp;//定义一个临时变量
//        for (int i = 0; i < nums.length - 1; i++) {
//            for (int j = 0; j < nums.length - i - 1; j++) {
//                if (nums[j + 1] < nums[j]) {
//                    temp = nums[j];
//                    nums[j] = nums[j + 1];
//                    nums[j + 1] = temp;
//                }
//            }
//        }
//        for (int num : nums) {
//            System.out.println("result:" + num);
//        }
    }


    public static List<List<Integer>> threeNum(int[] nums) {
//        if (nums.length == 0){
//            return new ArrayList<List<Integer>>();
//        }
//        Arrays.sort(nums);
//        int length = nums.length - 1;
//        int startIndex = 0;
//        int endIndex = length;
//        int start = nums[0];
//        int end = nums[length];
//        Set<List<Integer>> list = new HashSet<>();
//        while (startIndex != endIndex) {
//            int sum = start + end;
//            if (sum <= 0) {
//                for (int i = endIndex - 1; i > startIndex; i--) {
//                    int num = nums[i];
//                    int i1 = num + sum;
//                    if (i1 == 0) {
//                        List<Integer> res = new ArrayList<>();
//                        res.add(start);
//                        res.add(num);
//                        res.add(end);
//                        list.add(res);
//                    }
//                }
//                startIndex++;
//                start = nums[startIndex];
//            } else {
//                for (int i = startIndex + 1; i < endIndex; i++) {
//                    int num = nums[startIndex + 1];
//                    if (num + sum == 0) {
//                        List<Integer> res = new ArrayList<>();
//                        res.add(start);
//                        res.add(num);
//                        res.add(end);
//                        list.add(res);
//                        break;
//                    }
//                }
//                endIndex--;
//                end = nums[endIndex];
//            }
//        }
//        return new ArrayList<List<Integer>>(list);
//        int[][] arr = new int[list.size()][3];
//        List <List<Integer>> lst = new ArrayList<List<Integer>>(list);
//        int flag = 0;
//        for (int i = 0 ;i < arr .length ; i++){
//            int[] ints = arr[i];
//            for (int j = 0 ; j < lst .size() ; j++){
//                if (j == i){
//                    List<Integer> integers = lst.get(j);
//                    ints[0] = integers.get(0);
//                    ints[1] = integers.get(1);
//                    ints[2] = integers.get(2);
//                    break;
//                }
//            }
//        }
//        return arr;


        Arrays.sort(nums);//排序，nums变成递增数组
        List<List<Integer>> res = new ArrayList<>();
        //k < nums.length - 2是为了保证后面还能存在两个数字
        for (int k = 0; k < nums.length - 2; k++) {
            //若nums[k]大于0，则后面的数字也是大于零（排序后是递增的）
            if (nums[k] > 0) break;
            //nums[k]值重复了，去重
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            //定义左右指针
            int i = k + 1, j = nums.length - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    while (i < j && nums[i] == nums[++i]) ;//左指针前进并去重
                } else if (sum > 0) {
                    while (i < j && nums[j] == nums[--j]) ;//右指针后退并去重
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while (i < j && nums[i] == nums[++i]) ;//左指针前进并去重
                    while (i < j && nums[j] == nums[--j]) ;//右指针后退并去重
                }
            }
        }
        return res;

    }
}
